package oj;

import java.util.*;

public class Num373 {
    private class Freq{
        //第一个数组元素
        int u;
        //第二个数组元素
        int v;

        public Freq(int u, int v) {
            this.u = u;
            this.v = v;
        }
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
       Queue<Freq> queue=new PriorityQueue<>(new Comparator<Freq>() {
           @Override
           public int compare(Freq o1, Freq o2) {
               return (o2.u+o2.v)-(o1.u+o1.v);
           }
       });
       //最外层取u值
        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            //最内层取v值
            for (int j = 0; j < Math.min(k, nums2.length); j++) {
                if(queue.size()<k){
                    queue.offer(new Freq(nums1[i],nums2[j]));
                }else {
                    Freq freq= queue.peek();
                    if(nums1[i] + nums2[j] < freq.u+ freq.v){
                        queue.poll();
                        queue.offer(new Freq(nums1[i],nums2[j] ));
                    }
                }
            }
        }
        //队列中存储了前k个最小freq对象
        List<List<Integer>> ret=new ArrayList<>();
        //边界条件 k>queue.size()
        for (int i = 0; i < k && !queue.isEmpty(); i++) {
            List<Integer> tmp=new ArrayList<>();
            Freq freq= queue.poll();
            tmp.add(freq.u);
            tmp.add(freq.v);
            ret.add(tmp);
        }
        return ret;
    }
}
